class Solution:
    def minCost(self, n: int, cuts: list[int]) -> int:
        cuts.sort()
        memory = dict()

        def dp(left, right):
            if (left, right) in memory: return memory[(left, right)]
            length = right - left
            res = 0
            for cut in cuts:
                if left < cut < right:
                    if res == 0:
                        res = length + dp(left, cut) + dp(cut, right)
                    else:
                        res = min(res, length + dp(left, cut) + dp(cut, right))
            memory[(left, right)] = res
            return memory[(left, right)]

        return dp(0, n)
